#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

bool isMatch(char* s, char* p);

int main()
{
	char s[] = "abcd", p[] = "d*";
	bool res = isMatch(s, p);
	printf("res: %s\n", res ? "true" : "false");
	return 0;
}

bool isMatch(char* s, char* p)
{
	int s_len = strlen(s), p_len = strlen(p);
	// 插入哨兵 ␣ , 〄舒服的边界处理♡
	char *str = calloc(s_len + 2, sizeof(char)),
		 *pattern = calloc(p_len + 2, sizeof(char));
	str[0] = ' ', strcat(str, s);
	pattern[0] = ' ', strcat(pattern, p);
	free(s); free(p);

	char dp[s_len + 1][p_len + 1]; memset(dp, 0, sizeof(dp)); 
	dp[0][0] = true;
	for (int i = 0; i <= s_len; i++)
		for (int j = 1; j <= p_len; j++) {
			if (j + 1 <= p_len && pattern[j + 1] == '*') continue;

			if (i - 1 >= 0 && pattern[j] != '*')
				dp[i][j] = dp[i - 1][j - 1] && (str[i] == pattern[j] || pattern[j] == '.');
			else if (pattern[j] == '*')
				dp[i][j] = (j - 2 >= 0 && dp[i][j - 2]) || (i - 1 >= 0 && dp[i - 1][j] && (str[i] == pattern[j - 1] || pattern[j - 1] == '.'));
		}

	return dp[s_len][p_len];
}
